#include <bits/stdc++.h>
// 2025/01/19
// tag: 
// Author: Zhang Muen
using namespace std;

int g[1000001], f[1000001];

/*
G[N]=F[N-1]+G[N-1]
F[N]=F[N-1]+F[N-2]+2*G[N-2]
*/

signed main()
{
    int n;
    cin >> n;
    f[1] = g[1] = 1, f[0] = 1;
    for (int i = 2; i <= n; i++){
        f[i] = f[i - 1] + f[i - 2] + 2 * g[i - 2];
        g[i] = f[i - 1] + g[i - 1];
        f[i] %= 10000, g[i] %= 10000;
    }
    cout << f[n] << endl;
    return 0;
}